package com.baomidou.kisso.common.bcprov.math.ec;

import java.math.BigInteger;
import java.util.Random;

import com.baomidou.kisso.common.bcprov.util.Arrays;
import com.baomidou.kisso.common.bcprov.util.BigIntegers;

public abstract class ECFieldElement implements ECConstants {

	public abstract BigInteger toBigInteger();


	public abstract String getFieldName();


	public abstract int getFieldSize();


	public abstract ECFieldElement add( ECFieldElement b );


	public abstract ECFieldElement addOne();


	public abstract ECFieldElement subtract( ECFieldElement b );


	public abstract ECFieldElement multiply( ECFieldElement b );


	public abstract ECFieldElement divide( ECFieldElement b );


	public abstract ECFieldElement negate();


	public abstract ECFieldElement square();


	public abstract ECFieldElement invert();


	public abstract ECFieldElement sqrt();


	public int bitLength() {
		return toBigInteger().bitLength();
	}


	public boolean isZero() {
		return 0 == toBigInteger().signum();
	}


	public boolean testBitZero() {
		return toBigInteger().testBit(0);
	}


	public String toString() {
		return this.toBigInteger().toString(16);
	}


	public byte[] getEncoded() {
		return BigIntegers.asUnsignedByteArray((getFieldSize() + 7) / 8, toBigInteger());
	}

	public static class Fp extends ECFieldElement {

		BigInteger q, r, x;


		//        static int[] calculateNaf(BigInteger p)
		//        {
		//            int[] naf = WNafUtil.generateCompactNaf(p);
		//
		//            int bit = 0;
		//            for (int i = 0; i < naf.length; ++i)
		//            {
		//                int ni = naf[i];
		//                int digit = ni >> 16, zeroes = ni & 0xFFFF;
		//
		//                bit += zeroes;
		//                naf[i] = digit < 0 ? ~bit : bit;
		//                ++bit;
		//            }
		//
		//            int last = naf.length - 1;
		//            if (last > 0 && last <= 16)
		//            {
		//                int top = naf[last], top2 = naf[last - 1];
		//                if (top2 < 0)
		//                {
		//                    top2 = ~top2;
		//                }
		//                if (top - top2 >= 64)
		//                {
		//                    return naf;
		//                }
		//            }
		//
		//            return null;
		//        }

		static BigInteger calculateResidue( BigInteger p ) {
			int bitLength = p.bitLength();
			if ( bitLength > 128 ) {
				BigInteger firstWord = p.shiftRight(bitLength - 64);
				if ( firstWord.longValue() == -1L ) {
					return ONE.shiftLeft(bitLength).subtract(p);
				}
			}
			return null;
		}


		/**
		 * @deprecated Use ECCurve.fromBigInteger to construct field elements
		 */
		public Fp( BigInteger q, BigInteger x ) {
			this(q, calculateResidue(q), x);
		}


		Fp( BigInteger q, BigInteger r, BigInteger x ) {
			if ( x == null || x.signum() < 0 || x.compareTo(q) >= 0 ) {
				throw new IllegalArgumentException("x value invalid in Fp field element");
			}

			this.q = q;
			this.r = r;
			this.x = x;
		}


		public BigInteger toBigInteger() {
			return x;
		}


		/**
		 * return the field name for this field.
		 *
		 * @return the string "Fp".
		 */
		public String getFieldName() {
			return "Fp";
		}


		public int getFieldSize() {
			return q.bitLength();
		}


		public BigInteger getQ() {
			return q;
		}


		public ECFieldElement add( ECFieldElement b ) {
			return new Fp(q, r, modAdd(x, b.toBigInteger()));
		}


		public ECFieldElement addOne() {
			BigInteger x2 = x.add(ECConstants.ONE);
			if ( x2.compareTo(q) == 0 ) {
				x2 = ECConstants.ZERO;
			}
			return new Fp(q, r, x2);
		}


		public ECFieldElement subtract( ECFieldElement b ) {
			BigInteger x2 = b.toBigInteger();
			BigInteger x3 = x.subtract(x2);
			if ( x3.signum() < 0 ) {
				x3 = x3.add(q);
			}
			return new Fp(q, r, x3);
		}


		public ECFieldElement multiply( ECFieldElement b ) {
			return new Fp(q, r, modMult(x, b.toBigInteger()));
		}


		public ECFieldElement divide( ECFieldElement b ) {
			return new Fp(q, modMult(x, b.toBigInteger().modInverse(q)));
		}


		public ECFieldElement negate() {
			BigInteger x2;
			if ( x.signum() == 0 ) {
				x2 = x;
			} else if ( ONE.equals(r) ) {
				x2 = q.xor(x);
			} else {
				x2 = q.subtract(x);
			}
			return new Fp(q, r, x2);
		}


		public ECFieldElement square() {
			return new Fp(q, r, modMult(x, x));
		}


		public ECFieldElement invert() {
			// TODO Modular inversion can be faster for a (Generalized) Mersenne Prime.
			return new Fp(q, r, x.modInverse(q));
		}


		// D.1.4 91
		/**
		 * return a sqrt root - the routine verifies that the calculation
		 * returns the right value - if none exists it returns null.
		 */
		public ECFieldElement sqrt() {
			if ( !q.testBit(0) ) {
				throw new RuntimeException("not done yet");
			}

			// note: even though this class implements ECConstants don't be tempted to
			// remove the explicit declaration, some J2ME environments don't cope.
			// p mod 4 == 3
			if ( q.testBit(1) ) {
				// z = g^(u+1) + p, p = 4u + 3
				ECFieldElement z = new Fp(q, r, x.modPow(q.shiftRight(2).add(ECConstants.ONE), q));

				return z.square().equals(this) ? z : null;
			}

			// p mod 4 == 1
			BigInteger qMinusOne = q.subtract(ECConstants.ONE);

			BigInteger legendreExponent = qMinusOne.shiftRight(1);
			if ( !(x.modPow(legendreExponent, q).equals(ECConstants.ONE)) ) {
				return null;
			}

			BigInteger u = qMinusOne.shiftRight(2);
			BigInteger k = u.shiftLeft(1).add(ECConstants.ONE);

			BigInteger Q = this.x;
			BigInteger fourQ = modDouble(modDouble(Q));

			BigInteger U, V;
			Random rand = new Random();
			do {
				BigInteger P;
				do {
					P = new BigInteger(q.bitLength(), rand);
				} while ( P.compareTo(q) >= 0
						|| !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, q).equals(qMinusOne)) );

				BigInteger[] result = lucasSequence(P, Q, k);
				U = result[0];
				V = result[1];

				if ( modMult(V, V).equals(fourQ) ) {
					// Integer division by 2, mod q
					if ( V.testBit(0) ) {
						V = V.add(q);
					}

					V = V.shiftRight(1);

					//assert V.multiply(V).mod(q).equals(x);

					return new ECFieldElement.Fp(q, r, V);
				}
			} while ( U.equals(ECConstants.ONE) || U.equals(qMinusOne) );

			return null;

			//            BigInteger qMinusOne = q.subtract(ECConstants.ONE);
			//            BigInteger legendreExponent = qMinusOne.shiftRight(1); //divide(ECConstants.TWO);
			//            if (!(x.modPow(legendreExponent, q).equals(ECConstants.ONE)))
			//            {
			//                return null;
			//            }
			//
			//            Random rand = new Random();
			//            BigInteger fourX = x.shiftLeft(2);
			//
			//            BigInteger r;
			//            do
			//            {
			//                r = new BigInteger(q.bitLength(), rand);
			//            }
			//            while (r.compareTo(q) >= 0
			//                || !(r.multiply(r).subtract(fourX).modPow(legendreExponent, q).equals(qMinusOne)));
			//
			//            BigInteger n1 = qMinusOne.shiftRight(2); //.divide(ECConstants.FOUR);
			//            BigInteger n2 = n1.add(ECConstants.ONE); //q.add(ECConstants.THREE).divide(ECConstants.FOUR);
			//
			//            BigInteger wOne = WOne(r, x, q);
			//            BigInteger wSum = W(n1, wOne, q).add(W(n2, wOne, q)).mod(q);
			//            BigInteger twoR = r.shiftLeft(1); //ECConstants.TWO.multiply(r);
			//
			//            BigInteger root = twoR.modPow(q.subtract(ECConstants.TWO), q)
			//                .multiply(x).mod(q)
			//                .multiply(wSum).mod(q);
			//
			//            return new Fp(q, root);
		}


		//        private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p)
		//        {
		//            if (n.equals(ECConstants.ONE))
		//            {
		//                return wOne;
		//            }
		//            boolean isEven = !n.testBit(0);
		//            n = n.shiftRight(1);//divide(ECConstants.TWO);
		//            if (isEven)
		//            {
		//                BigInteger w = W(n, wOne, p);
		//                return w.multiply(w).subtract(ECConstants.TWO).mod(p);
		//            }
		//            BigInteger w1 = W(n.add(ECConstants.ONE), wOne, p);
		//            BigInteger w2 = W(n, wOne, p);
		//            return w1.multiply(w2).subtract(wOne).mod(p);
		//        }
		//
		//        private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p)
		//        {
		//            return r.multiply(r).multiply(x.modPow(q.subtract(ECConstants.TWO), q)).subtract(ECConstants.TWO).mod(p);
		//        }

		private BigInteger[] lucasSequence( BigInteger P, BigInteger Q, BigInteger k ) {
			int n = k.bitLength();
			int s = k.getLowestSetBit();

			BigInteger Uh = ECConstants.ONE;
			BigInteger Vl = ECConstants.TWO;
			BigInteger Vh = P;
			BigInteger Ql = ECConstants.ONE;
			BigInteger Qh = ECConstants.ONE;

			for ( int j = n - 1 ; j >= s + 1 ; --j ) {
				Ql = modMult(Ql, Qh);

				if ( k.testBit(j) ) {
					Qh = modMult(Ql, Q);
					Uh = modMult(Uh, Vh);
					Vl = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
					Vh = modReduce(Vh.multiply(Vh).subtract(Qh.shiftLeft(1)));
				} else {
					Qh = Ql;
					Uh = modReduce(Uh.multiply(Vl).subtract(Ql));
					Vh = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
					Vl = modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
				}
			}

			Ql = modMult(Ql, Qh);
			Qh = modMult(Ql, Q);
			Uh = modReduce(Uh.multiply(Vl).subtract(Ql));
			Vl = modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
			Ql = modMult(Ql, Qh);

			for ( int j = 1 ; j <= s ; ++j ) {
				Uh = modMult(Uh, Vl);
				Vl = modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
				Ql = modMult(Ql, Ql);
			}

			return new BigInteger[ ] { Uh, Vl };
		}


		protected BigInteger modAdd( BigInteger x1, BigInteger x2 ) {
			BigInteger x3 = x1.add(x2);
			if ( x3.compareTo(q) >= 0 ) {
				x3 = x3.subtract(q);
			}
			return x3;
		}


		protected BigInteger modDouble( BigInteger x ) {
			BigInteger _2x = x.shiftLeft(1);
			if ( _2x.compareTo(q) >= 0 ) {
				_2x = _2x.subtract(q);
			}
			return _2x;
		}


		protected BigInteger modMult( BigInteger x1, BigInteger x2 ) {
			return modReduce(x1.multiply(x2));
		}


		protected BigInteger modReduce( BigInteger x ) {
			//            if (naf != null)
			//            {
			//                int last = naf.length - 1;
			//                int bits = naf[last];
			//                while (x.bitLength() > (bits + 1))
			//                {
			//                    BigInteger u = x.shiftRight(bits);
			//                    BigInteger v = x.subtract(u.shiftLeft(bits));
			//
			//                    x = v;
			//
			//                    for (int i = 0; i < last; ++i)
			//                    {
			//                        int ni = naf[i];
			//                        if (ni < 0)
			//                        {
			//                            x = x.add(u.shiftLeft(~ni));
			//                        }
			//                        else
			//                        {
			//                            x = x.subtract(u.shiftLeft(ni));
			//                        }
			//                    }
			//                }
			//                while (x.compareTo(q) >= 0)
			//                {
			//                    x = x.subtract(q);
			//                }
			//            }
			//            else
			if ( r != null ) {
				int qLen = q.bitLength();
				while ( x.bitLength() > (qLen + 1) ) {
					BigInteger u = x.shiftRight(qLen);
					BigInteger v = x.subtract(u.shiftLeft(qLen));
					if ( !r.equals(ONE) ) {
						u = u.multiply(r);
					}
					x = u.add(v);
				}
				while ( x.compareTo(q) >= 0 ) {
					x = x.subtract(q);
				}
			} else {
				x = x.mod(q);
			}
			return x;
		}


		public boolean equals( Object other ) {
			if ( other == this ) {
				return true;
			}

			if ( !(other instanceof ECFieldElement.Fp) ) {
				return false;
			}

			ECFieldElement.Fp o = (ECFieldElement.Fp) other;
			return q.equals(o.q) && x.equals(o.x);
		}


		public int hashCode() {
			return q.hashCode() ^ x.hashCode();
		}
	}

	//    /**
	//     * Class representing the Elements of the finite field
	//     * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
	//     * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
	//     * basis representations are supported. Gaussian normal basis (GNB)
	//     * representation is not supported.
	//     */
	//    public static class F2m extends ECFieldElement
	//    {
	//        BigInteger x;
	//
	//        /**
	//         * Indicates gaussian normal basis representation (GNB). Number chosen
	//         * according to X9.62. GNB is not implemented at present.
	//         */
	//        public static final int GNB = 1;
	//
	//        /**
	//         * Indicates trinomial basis representation (TPB). Number chosen
	//         * according to X9.62.
	//         */
	//        public static final int TPB = 2;
	//
	//        /**
	//         * Indicates pentanomial basis representation (PPB). Number chosen
	//         * according to X9.62.
	//         */
	//        public static final int PPB = 3;
	//
	//        /**
	//         * TPB or PPB.
	//         */
	//        private int representation;
	//
	//        /**
	//         * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
	//         */
	//        private int m;
	//
	//        /**
	//         * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
	//         * x<sup>k</sup> + 1</code> represents the reduction polynomial
	//         * <code>f(z)</code>.<br>
	//         * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.<br>
	//         */
	//        private int k1;
	//
	//        /**
	//         * TPB: Always set to <code>0</code><br>
	//         * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.<br>
	//         */
	//        private int k2;
	//
	//        /**
	//         * TPB: Always set to <code>0</code><br>
	//         * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.<br>
	//         */
	//        private int k3;
	//        
	//        /**
	//         * Constructor for PPB.
	//         * @param m  The exponent <code>m</code> of
	//         * <code>F<sub>2<sup>m</sup></sub></code>.
	//         * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.
	//         * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.
	//         * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.
	//         * @param x The BigInteger representing the value of the field element.
	//         */
	//        public F2m(
	//            int m, 
	//            int k1, 
	//            int k2, 
	//            int k3,
	//            BigInteger x)
	//        {
	////            super(x);
	//            this.x = x;
	//
	//            if ((k2 == 0) && (k3 == 0))
	//            {
	//                this.representation = TPB;
	//            }
	//            else
	//            {
	//                if (k2 >= k3)
	//                {
	//                    throw new IllegalArgumentException(
	//                            "k2 must be smaller than k3");
	//                }
	//                if (k2 <= 0)
	//                {
	//                    throw new IllegalArgumentException(
	//                            "k2 must be larger than 0");
	//                }
	//                this.representation = PPB;
	//            }
	//
	//            if (x.signum() < 0)
	//            {
	//                throw new IllegalArgumentException("x value cannot be negative");
	//            }
	//
	//            this.m = m;
	//            this.k1 = k1;
	//            this.k2 = k2;
	//            this.k3 = k3;
	//        }
	//
	//        /**
	//         * Constructor for TPB.
	//         * @param m  The exponent <code>m</code> of
	//         * <code>F<sub>2<sup>m</sup></sub></code>.
	//         * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
	//         * x<sup>k</sup> + 1</code> represents the reduction
	//         * polynomial <code>f(z)</code>.
	//         * @param x The BigInteger representing the value of the field element.
	//         */
	//        public F2m(int m, int k, BigInteger x)
	//        {
	//            // Set k1 to k, and set k2 and k3 to 0
	//            this(m, k, 0, 0, x);
	//        }
	//
	//        public BigInteger toBigInteger()
	//        {
	//            return x;
	//        }
	//
	//        public String getFieldName()
	//        {
	//            return "F2m";
	//        }
	//
	//        public int getFieldSize()
	//        {
	//            return m;
	//        }
	//
	//        /**
	//         * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
	//         * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
	//         * (having the same representation).
	//         * @param a field element.
	//         * @param b field element to be compared.
	//         * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
	//         * are not elements of the same field
	//         * <code>F<sub>2<sup>m</sup></sub></code> (having the same
	//         * representation). 
	//         */
	//        public static void checkFieldElements(
	//            ECFieldElement a,
	//            ECFieldElement b)
	//        {
	//            if ((!(a instanceof F2m)) || (!(b instanceof F2m)))
	//            {
	//                throw new IllegalArgumentException("Field elements are not "
	//                        + "both instances of ECFieldElement.F2m");
	//            }
	//
	//            if ((a.toBigInteger().signum() < 0) || (b.toBigInteger().signum() < 0))
	//            {
	//                throw new IllegalArgumentException(
	//                        "x value may not be negative");
	//            }
	//
	//            ECFieldElement.F2m aF2m = (ECFieldElement.F2m)a;
	//            ECFieldElement.F2m bF2m = (ECFieldElement.F2m)b;
	//
	//            if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
	//                    || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
	//            {
	//                throw new IllegalArgumentException("Field elements are not "
	//                        + "elements of the same field F2m");
	//            }
	//
	//            if (aF2m.representation != bF2m.representation)
	//            {
	//                // Should never occur
	//                throw new IllegalArgumentException(
	//                        "One of the field "
	//                                + "elements are not elements has incorrect representation");
	//            }
	//        }
	//
	//        /**
	//         * Computes <code>z * a(z) mod f(z)</code>, where <code>f(z)</code> is
	//         * the reduction polynomial of <code>this</code>.
	//         * @param a The polynomial <code>a(z)</code> to be multiplied by
	//         * <code>z mod f(z)</code>.
	//         * @return <code>z * a(z) mod f(z)</code>
	//         */
	//        private BigInteger multZModF(final BigInteger a)
	//        {
	//            // Left-shift of a(z)
	//            BigInteger az = a.shiftLeft(1);
	//            if (az.testBit(this.m)) 
	//            {
	//                // If the coefficient of z^m in a(z) equals 1, reduction
	//                // modulo f(z) is performed: Add f(z) to to a(z):
	//                // Step 1: Unset mth coeffient of a(z)
	//                az = az.clearBit(this.m);
	//
	//                // Step 2: Add r(z) to a(z), where r(z) is defined as
	//                // f(z) = z^m + r(z), and k1, k2, k3 are the positions of
	//                // the non-zero coefficients in r(z)
	//                az = az.flipBit(0);
	//                az = az.flipBit(this.k1);
	//                if (this.representation == PPB) 
	//                {
	//                    az = az.flipBit(this.k2);
	//                    az = az.flipBit(this.k3);
	//                }
	//            }
	//            return az;
	//        }
	//
	//        public ECFieldElement add(final ECFieldElement b)
	//        {
	//            // No check performed here for performance reasons. Instead the
	//            // elements involved are checked in ECPoint.F2m
	//            // checkFieldElements(this, b);
	//            if (b.toBigInteger().signum() == 0)
	//            {
	//                return this;
	//            }
	//
	//            return new F2m(this.m, this.k1, this.k2, this.k3, this.x.xor(b.toBigInteger()));
	//        }
	//
	//        public ECFieldElement subtract(final ECFieldElement b)
	//        {
	//            // Addition and subtraction are the same in F2m
	//            return add(b);
	//        }
	//
	//
	//        public ECFieldElement multiply(final ECFieldElement b)
	//        {
	//            // Left-to-right shift-and-add field multiplication in F2m
	//            // Input: Binary polynomials a(z) and b(z) of degree at most m-1
	//            // Output: c(z) = a(z) * b(z) mod f(z)
	//
	//            // No check performed here for performance reasons. Instead the
	//            // elements involved are checked in ECPoint.F2m
	//            // checkFieldElements(this, b);
	//            final BigInteger az = this.x;
	//            BigInteger bz = b.toBigInteger();
	//            BigInteger cz;
	//
	//            // Compute c(z) = a(z) * b(z) mod f(z)
	//            if (az.testBit(0)) 
	//            {
	//                cz = bz;
	//            } 
	//            else 
	//            {
	//                cz = ECConstants.ZERO;
	//            }
	//
	//            for (int i = 1; i < this.m; i++) 
	//            {
	//                // b(z) := z * b(z) mod f(z)
	//                bz = multZModF(bz);
	//
	//                if (az.testBit(i)) 
	//                {
	//                    // If the coefficient of x^i in a(z) equals 1, b(z) is added
	//                    // to c(z)
	//                    cz = cz.xor(bz);
	//                }
	//            }
	//            return new ECFieldElement.F2m(m, this.k1, this.k2, this.k3, cz);
	//        }
	//
	//
	//        public ECFieldElement divide(final ECFieldElement b)
	//        {
	//            // There may be more efficient implementations
	//            ECFieldElement bInv = b.invert();
	//            return multiply(bInv);
	//        }
	//
	//        public ECFieldElement negate()
	//        {
	//            // -x == x holds for all x in F2m
	//            return this;
	//        }
	//
	//        public ECFieldElement square()
	//        {
	//            // Naive implementation, can probably be speeded up using modular
	//            // reduction
	//            return multiply(this);
	//        }
	//
	//        public ECFieldElement invert()
	//        {
	//            // Inversion in F2m using the extended Euclidean algorithm
	//            // Input: A nonzero polynomial a(z) of degree at most m-1
	//            // Output: a(z)^(-1) mod f(z)
	//
	//            // u(z) := a(z)
	//            BigInteger uz = this.x;
	//            if (uz.signum() <= 0) 
	//            {
	//                throw new ArithmeticException("x is zero or negative, " +
	//                        "inversion is impossible");
	//            }
	//
	//            // v(z) := f(z)
	//            BigInteger vz = ECConstants.ZERO.setBit(m);
	//            vz = vz.setBit(0);
	//            vz = vz.setBit(this.k1);
	//            if (this.representation == PPB) 
	//            {
	//                vz = vz.setBit(this.k2);
	//                vz = vz.setBit(this.k3);
	//            }
	//
	//            // g1(z) := 1, g2(z) := 0
	//            BigInteger g1z = ECConstants.ONE;
	//            BigInteger g2z = ECConstants.ZERO;
	//
	//            // while u != 1
	//            while (!(uz.equals(ECConstants.ZERO))) 
	//            {
	//                // j := deg(u(z)) - deg(v(z))
	//                int j = uz.bitLength() - vz.bitLength();
	//
	//                // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
	//                if (j < 0) 
	//                {
	//                    final BigInteger uzCopy = uz;
	//                    uz = vz;
	//                    vz = uzCopy;
	//
	//                    final BigInteger g1zCopy = g1z;
	//                    g1z = g2z;
	//                    g2z = g1zCopy;
	//
	//                    j = -j;
	//                }
	//
	//                // u(z) := u(z) + z^j * v(z)
	//                // Note, that no reduction modulo f(z) is required, because
	//                // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
	//                // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
	//                // = deg(u(z))
	//                uz = uz.xor(vz.shiftLeft(j));
	//
	//                // g1(z) := g1(z) + z^j * g2(z)
	//                g1z = g1z.xor(g2z.shiftLeft(j));
	////                if (g1z.bitLength() > this.m) {
	////                    throw new ArithmeticException(
	////                            "deg(g1z) >= m, g1z = " + g1z.toString(16));
	////                }
	//            }
	//            return new ECFieldElement.F2m(
	//                    this.m, this.k1, this.k2, this.k3, g2z);
	//        }
	//
	//        public ECFieldElement sqrt()
	//        {
	//            throw new RuntimeException("Not implemented");
	//        }
	//
	//        /**
	//         * @return the representation of the field
	//         * <code>F<sub>2<sup>m</sup></sub></code>, either of
	//         * TPB (trinomial
	//         * basis representation) or
	//         * PPB (pentanomial
	//         * basis representation).
	//         */
	//        public int getRepresentation()
	//        {
	//            return this.representation;
	//        }
	//
	//        /**
	//         * @return the degree <code>m</code> of the reduction polynomial
	//         * <code>f(z)</code>.
	//         */
	//        public int getM()
	//        {
	//            return this.m;
	//        }
	//
	//        /**
	//         * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
	//         * x<sup>k</sup> + 1</code> represents the reduction polynomial
	//         * <code>f(z)</code>.<br>
	//         * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.<br>
	//         */
	//        public int getK1()
	//        {
	//            return this.k1;
	//        }
	//
	//        /**
	//         * @return TPB: Always returns <code>0</code><br>
	//         * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.<br>
	//         */
	//        public int getK2()
	//        {
	//            return this.k2;
	//        }
	//
	//        /**
	//         * @return TPB: Always set to <code>0</code><br>
	//         * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
	//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
	//         * represents the reduction polynomial <code>f(z)</code>.<br>
	//         */
	//        public int getK3()
	//        {
	//            return this.k3;
	//        }
	//
	//        public boolean equals(Object anObject)
	//        {
	//            if (anObject == this) 
	//            {
	//                return true;
	//            }
	//
	//            if (!(anObject instanceof ECFieldElement.F2m)) 
	//            {
	//                return false;
	//            }
	//
	//            ECFieldElement.F2m b = (ECFieldElement.F2m)anObject;
	//            
	//            return ((this.m == b.m) && (this.k1 == b.k1) && (this.k2 == b.k2)
	//                && (this.k3 == b.k3)
	//                && (this.representation == b.representation)
	//                && (this.x.equals(b.x)));
	//        }
	//
	//        public int hashCode()
	//        {
	//            return x.hashCode() ^ m ^ k1 ^ k2 ^ k3;
	//        }
	//    }

	/**
	 * Class representing the Elements of the finite field
	 * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
	 * representation. Both trinomial (TPB) and pentanomial (PPB) polynomial
	 * basis representations are supported. Gaussian normal basis (GNB)
	 * representation is not supported.
	 */
	public static class F2m extends ECFieldElement {

		/**
		 * Indicates gaussian normal basis representation (GNB). Number chosen
		 * according to X9.62. GNB is not implemented at present.
		 */
		public static final int GNB = 1;

		/**
		 * Indicates trinomial basis representation (TPB). Number chosen
		 * according to X9.62.
		 */
		public static final int TPB = 2;

		/**
		 * Indicates pentanomial basis representation (PPB). Number chosen
		 * according to X9.62.
		 */
		public static final int PPB = 3;

		/**
		 * TPB or PPB.
		 */
		private int representation;

		/**
		 * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
		 */
		private int m;

		//        /**
		//         * TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
		//         * x<sup>k</sup> + 1</code> represents the reduction polynomial
		//         * <code>f(z)</code>.<br>
		//         * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
		//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		//         * represents the reduction polynomial <code>f(z)</code>.<br>
		//         */
		//        private int k1;
		//
		//        /**
		//         * TPB: Always set to <code>0</code><br>
		//         * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
		//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		//         * represents the reduction polynomial <code>f(z)</code>.<br>
		//         */
		//        private int k2;
		//
		//        /**
		//         * TPB: Always set to <code>0</code><br>
		//         * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
		//         * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		//         * represents the reduction polynomial <code>f(z)</code>.<br>
		//         */
		//        private int k3;

		private int[] ks;

		/**
		 * The <code>LongArray</code> holding the bits.
		 */
		private LongArray x;


		/**
		 * Constructor for PPB.
		 * @param m  The exponent <code>m</code> of
		 * <code>F<sub>2<sup>m</sup></sub></code>.
		 * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
		 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		 * represents the reduction polynomial <code>f(z)</code>.
		 * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
		 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		 * represents the reduction polynomial <code>f(z)</code>.
		 * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
		 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		 * represents the reduction polynomial <code>f(z)</code>.
		 * @param x The BigInteger representing the value of the field element.
		 * @deprecated Use ECCurve.fromBigInteger to construct field elements
		 */
		public F2m( int m, int k1, int k2, int k3, BigInteger x ) {
			if ( (k2 == 0) && (k3 == 0) ) {
				this.representation = TPB;
				this.ks = new int[ ] { k1 };
			} else {
				if ( k2 >= k3 ) {
					throw new IllegalArgumentException("k2 must be smaller than k3");
				}
				if ( k2 <= 0 ) {
					throw new IllegalArgumentException("k2 must be larger than 0");
				}
				this.representation = PPB;
				this.ks = new int[ ] { k1, k2, k3 };
			}

			this.m = m;
			this.x = new LongArray(x);
		}


		/**
		 * Constructor for TPB.
		 * @param m  The exponent <code>m</code> of
		 * <code>F<sub>2<sup>m</sup></sub></code>.
		 * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
		 * x<sup>k</sup> + 1</code> represents the reduction
		 * polynomial <code>f(z)</code>.
		 * @param x The BigInteger representing the value of the field element.
		 * @deprecated Use ECCurve.fromBigInteger to construct field elements
		 */
		public F2m( int m, int k, BigInteger x ) {
			// Set k1 to k, and set k2 and k3 to 0
			this(m, k, 0, 0, x);
		}


		private F2m( int m, int[] ks, LongArray x ) {
			this.m = m;
			this.representation = (ks.length == 1) ? TPB : PPB;
			this.ks = ks;
			this.x = x;
		}


		public int bitLength() {
			return x.degree();
		}


		public boolean isZero() {
			return x.isZero();
		}


		public boolean testBitZero() {
			return x.testBitZero();
		}


		public BigInteger toBigInteger() {
			return x.toBigInteger();
		}


		public String getFieldName() {
			return "F2m";
		}


		public int getFieldSize() {
			return m;
		}


		/**
		 * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
		 * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
		 * (having the same representation).
		 * @param a field element.
		 * @param b field element to be compared.
		 * @throws IllegalArgumentException if <code>a</code> and <code>b</code>
		 * are not elements of the same field
		 * <code>F<sub>2<sup>m</sup></sub></code> (having the same
		 * representation). 
		 */
		public static void checkFieldElements( ECFieldElement a, ECFieldElement b ) {
			if ( (!(a instanceof F2m)) || (!(b instanceof F2m)) ) {
				throw new IllegalArgumentException("Field elements are not " + "both instances of ECFieldElement.F2m");
			}

			ECFieldElement.F2m aF2m = (ECFieldElement.F2m) a;
			ECFieldElement.F2m bF2m = (ECFieldElement.F2m) b;

			if ( aF2m.representation != bF2m.representation ) {
				// Should never occur
				throw new IllegalArgumentException("One of the F2m field elements has incorrect representation");
			}

			if ( (aF2m.m != bF2m.m) || !Arrays.areEqual(aF2m.ks, bF2m.ks) ) {
				throw new IllegalArgumentException("Field elements are not elements of the same field F2m");
			}
		}


		public ECFieldElement add( final ECFieldElement b ) {
			// No check performed here for performance reasons. Instead the
			// elements involved are checked in ECPoint.F2m
			// checkFieldElements(this, b);
			LongArray iarrClone = (LongArray) this.x.clone();
			F2m bF2m = (F2m) b;
			iarrClone.addShiftedByWords(bF2m.x, 0);
			return new F2m(m, ks, iarrClone);
		}


		public ECFieldElement addOne() {
			return new F2m(m, ks, x.addOne());
		}


		public ECFieldElement subtract( final ECFieldElement b ) {
			// Addition and subtraction are the same in F2m
			return add(b);
		}


		public ECFieldElement multiply( final ECFieldElement b ) {
			// Right-to-left comb multiplication in the LongArray
			// Input: Binary polynomials a(z) and b(z) of degree at most m-1
			// Output: c(z) = a(z) * b(z) mod f(z)

			// No check performed here for performance reasons. Instead the
			// elements involved are checked in ECPoint.F2m
			// checkFieldElements(this, b);
			return new F2m(m, ks, x.modMultiply(((F2m) b).x, m, ks));
		}


		public ECFieldElement divide( final ECFieldElement b ) {
			// There may be more efficient implementations
			ECFieldElement bInv = b.invert();
			return multiply(bInv);
		}


		public ECFieldElement negate() {
			// -x == x holds for all x in F2m
			return this;
		}


		public ECFieldElement square() {
			return new F2m(m, ks, x.modSquare(m, ks));
		}


		public ECFieldElement invert() {
			return new ECFieldElement.F2m(this.m, this.ks, this.x.modInverse(m, ks));
		}


		public ECFieldElement sqrt() {
			throw new RuntimeException("Not implemented");
		}


		/**
		 * @return the representation of the field
		 * <code>F<sub>2<sup>m</sup></sub></code>, either of
		 * TPB (trinomial
		 * basis representation) or
		 * PPB (pentanomial
		 * basis representation).
		 */
		public int getRepresentation() {
			return this.representation;
		}


		/**
		 * @return the degree <code>m</code> of the reduction polynomial
		 * <code>f(z)</code>.
		 */
		public int getM() {
			return this.m;
		}


		/**
		 * @return TPB: The integer <code>k</code> where <code>x<sup>m</sup> +
		 * x<sup>k</sup> + 1</code> represents the reduction polynomial
		 * <code>f(z)</code>.<br>
		 * PPB: The integer <code>k1</code> where <code>x<sup>m</sup> +
		 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		 * represents the reduction polynomial <code>f(z)</code>.<br>
		 */
		public int getK1() {
			return this.ks[0];
		}


		/**
		 * @return TPB: Always returns <code>0</code><br>
		 * PPB: The integer <code>k2</code> where <code>x<sup>m</sup> +
		 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		 * represents the reduction polynomial <code>f(z)</code>.<br>
		 */
		public int getK2() {
			return this.ks.length >= 2 ? this.ks[1] : 0;
		}


		/**
		 * @return TPB: Always set to <code>0</code><br>
		 * PPB: The integer <code>k3</code> where <code>x<sup>m</sup> +
		 * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
		 * represents the reduction polynomial <code>f(z)</code>.<br>
		 */
		public int getK3() {
			return this.ks.length >= 3 ? this.ks[2] : 0;
		}


		public boolean equals( Object anObject ) {
			if ( anObject == this ) {
				return true;
			}

			if ( !(anObject instanceof ECFieldElement.F2m) ) {
				return false;
			}

			ECFieldElement.F2m b = (ECFieldElement.F2m) anObject;

			return ((this.m == b.m)
					&& (this.representation == b.representation) && Arrays.areEqual(this.ks, b.ks)
					&& (this.x.equals(b.x)));
		}


		public int hashCode() {
			return x.hashCode() ^ m ^ Arrays.hashCode(ks);
		}
	}
}
